package leetcode.code0099;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;
import leetcode.helper.tree.TreeArray;
import leetcode.helper.tree.TreeNode;

public class Solution implements IDebug {

	TreeNode last;
	TreeNode wrong1;
	TreeNode wrong2;

	public void recoverTree(TreeNode root) {
		this.recover(root);
		int tmp = wrong2.val;
		wrong2.val = wrong1.val;
		wrong1.val = tmp;
	}

	private void recover(TreeNode root) {
		if (root == null) {
			return;
		}
		this.recover(root.left);
		if (last == null || root.val > last.val) {
			last = root;
		} else {
			if (wrong1 == null) {
				wrong1 = last;
				wrong2 = root;
			} else {
				wrong2 = root;
			}
			last = root;
		}
		this.recover(root.right);
	}

	public TreeNode[] nodes;

	public void debug7() {
		this.recoverTree(TreeArray.array2tree(HelpDebug.str2array4("[3,1,4,null,null,2]")));
	}
	public void debug0() {
		TreeNode root = TreeArray.array2tree(HelpDebug.str2array4("[3,1,null,null,2]"));
		this.recoverTree(TreeArray.array2tree(HelpDebug.str2array4("[1,3,null,null,2]")));
	}

	@Override
	public void debug1() {
		nodes = new TreeNode[11];
		int[] vals = new int[] { 0, 1, 2, 3, 4, 7, 6, 5, 8, 9, 10 };
		TreeNode root = this.treeNode(vals[5]);
		this.treeNode(vals[5]).left = this.treeNode(vals[3]);
		this.treeNode(vals[5]).right = this.treeNode(vals[9]);
		this.treeNode(vals[3]).left = this.treeNode(vals[1]);
		this.treeNode(vals[3]).right = this.treeNode(vals[4]);
		this.treeNode(vals[9]).left = this.treeNode(vals[7]);
		this.treeNode(vals[9]).right = this.treeNode(vals[10]);
		this.treeNode(vals[7]).left = this.treeNode(vals[6]);
		this.treeNode(vals[7]).right = this.treeNode(vals[8]);
		this.recoverTree(root);
//		System.out.println(root);
	}

	private TreeNode treeNode(int val) {
		if (nodes[val] != null) {
			return nodes[val];
		}
		nodes[val] = new TreeNode(val);
		return nodes[val];
	}

	@Override
	public void debug2() {
		TreeNode root = TreeArray.array2tree(HelpDebug.str2array4("[3,1,4,null,null,2]"));
		this.recoverTree(root);

	}

	@Override
	public void debug3() {
		TreeNode root = TreeArray.array2tree(HelpDebug.str2array4("[2,3,1]"));
		this.recoverTree(root);
//		System.out.println(root);
	}

	@Override
	public void debug4() {
		TreeNode root = TreeArray.array2tree(HelpDebug.str2array4("[1,3,null,null,2]"));
		this.recoverTree(root);
//		System.out.println(root);

	}

	public void debug5() {
		TreeNode root = TreeArray.array2tree(HelpDebug.str2array4("[5,7,9,1,4,3,10,null,null,null,null,6,8]"));
		this.recoverTree(root);
//		System.out.println(root);

	}

	public void debug6() {
		TreeNode root = TreeArray.array2tree(HelpDebug.str2array4("[1,3,null,null,2]"));
		this.recoverTree(root);
//		System.out.println(root);

	}

	public static void main(String[] args) {
		Solution so = new Solution();
//		so.debug6();
//		so.debug5();
//		so.debug4();
//		so.debug3();
//		so.debug2();
//		so.debug1();
//		so.debug0();
		so.debug7();

	}

}
